#include <stdio.h>
#include <stdlib.h>
#include <set>
int timeSegSum;
int switchableSum;
int classroomSum;
int roadSum;
// classCIndeces[i]表示时间段i上在第一节的教室编号
int* classCIndeces;
// classCIndeces[i]表示时间段i上在第二节的教室编号
int* classDIndeces;
// probabilities[i]表示时间段上从C教室换到D教室的通过概率
float* probabilities;
// roadCoast[j]表示第j条道路的信息，roadCoast[j][0]表示教室1，roadCoast[j][0]表示教室2，roadCoast[j][2]表示体力消耗
int (*roadCoast)[3];


int roadGraph[3][3];

int shortestRoad(int classroom1, int classroom2) {
    // 初始化
    int dist[3] = {INT32_MAX, INT32_MAX, INT32_MAX};
    dist[classroom1] = 0;
    // S集合
    std::set<int> sSet;
    sSet.insert(classroom1);
    std::set<int> uSet;
    for (int i = 0; i < classroomSum; i++) {
        if (i != classroom1) {
            uSet.insert(i);
        }
    }
    
    // 将直接与classroom1相邻的顶点的cost放在dist中
    for(int i = 0; i < roadSum; i++) {
        int room1 = roadCoast[i][0] - 1;
        int room2 = roadCoast[i][1] - 1;
        if (classroom1 == room1) {
            dist[room2] = roadCoast[i][2];
        } else if (classroom1 == room2) {
            dist[room1] = roadCoast[i][2];
        }
    }
    
    int currentClassroom = classroom1;
    while (uSet.size() > 0) {
        int adjacentRoom = -1;
        int cost = INT32_MAX;
        for(int i = 0; i < roadSum; i++) {
            int room1 = roadCoast[i][0] - 1;
            int room2 = roadCoast[i][1] - 1;
            if (currentClassroom == room1) {
                if (sSet.find(room2) == sSet.end() && roadCoast[i][2] < cost) {
                    adjacentRoom = room2;
                    cost = roadCoast[i][2];
                }
            } else if (currentClassroom == room2) {
                if (sSet.find(room1) == sSet.end() && roadCoast[i][2] < cost) {
                    adjacentRoom = room1;
                    cost = roadCoast[i][2];
                }
            }
        }
        if (adjacentRoom == -1 || cost == INT32_MAX) {
            break;
        }
        int currentCost = dist[currentClassroom];
        int adjacentRoomOriginalCost = dist[adjacentRoom];
        if ((currentCost + cost) < adjacentRoomOriginalCost) {
            dist[adjacentRoom] = currentCost + cost;
        }
        sSet.insert(adjacentRoom);
        uSet.erase(adjacentRoom);
        currentClassroom = adjacentRoom;
    }
//    printf("%d shortest cost array: [", classroom1 + 1);
//    for(int i  = 0; i < classroomSum; i++) {
//        printf("%d:%d%s", i+1, dist[i], (i==classroomSum-1) ? "" : " ");
//    }
//    printf("], %d to %d shortest cost is %d\n", classroom1+1, classroom2+1, dist[classroom2]);
    return dist[classroom2];
}

int energyCost(int classroomIndex1, int classroomIndex2) {
    // -1的情况为初始化的情况
    if (classroomIndex1 == -1 || classroomIndex2 == -1) {
        return 0;
    }
    if (classroomIndex1 == classroomIndex2) {
        return 0;
    }
    return shortestRoad(classroomIndex1 - 1, classroomIndex2 - 1);
}

float min(float except1, float except2) {
    return except1 < except2 ? except1 : except2;
}

float calculateException(int* classes, int currentTimeSegIndex, int currentClass, int cost, float probability) {
    if (currentTimeSegIndex == timeSegSum - 1) {
        return cost * probability;
    }
    int nextClass = classes[currentTimeSegIndex + 1];
    // 下一节课在C教室的编号
    int nextCClassroomIndex = classCIndeces[currentTimeSegIndex + 1];
    // 下一节课在D教室的编号
    int nextDClassroomIndex = classDIndeces[currentTimeSegIndex + 1];
    // 当前教室去到下一个C教室耗费的体力
    int nextCEnergyCost = energyCost(currentClass, nextCClassroomIndex);
    // 当前教室去到下一个D教室耗费的体力
    int nextDEnergyCost = energyCost(currentClass, nextDClassroomIndex);
    // 如果想在C教室上课，则不需要申请
    if (nextClass == nextCClassroomIndex) {
        float except = calculateException(classes, currentTimeSegIndex + 1, nextClass, nextCEnergyCost + cost, probability * 1.0);
//        printf("calculateException1 currentTimeSegIndex = %d, currentClass %d, cost = %d, probability = %.2f, nextclass = %d, nextCCost = %d, except = %.2f\n",
//               currentTimeSegIndex, currentClass, cost, probability, nextCClassroomIndex, nextCEnergyCost + cost, except);
        return except;
    } else { // 如果想D教室上课，那么有一定的概率在C教室上课，也有一定的概率在D教室上课
        // 下一节课在C教室上的概率
        float cProbability = 1 - probabilities[currentTimeSegIndex + 1];
        // 下一节课在D教室上的概率
        float dProbability = probabilities[currentTimeSegIndex + 1];
        float exceptC = calculateException(classes, currentTimeSegIndex + 1, nextCClassroomIndex, nextCEnergyCost + cost, probability * cProbability);
        float exceptD = calculateException(classes, currentTimeSegIndex + 1, nextDClassroomIndex, nextDEnergyCost + cost, probability * dProbability);
        float except = exceptC + exceptD;
//        printf("calculateException2 currentTimeSegIndex = %d, currentClass = %d, cost = %d, probability = %.2f, nextCClass = %d, nextDClass = %d, nextCCost = %d, nextDCost = %d\n",
//               currentTimeSegIndex, currentClass, cost, probability, nextCClassroomIndex, nextDClassroomIndex, nextCEnergyCost, nextDEnergyCost);
//        printf("newCCost = %d, newDCost = %d, newCProbability = %.2f, newDProbability = %.2f, exceptC = %.2f, exceptD = %.2f, except = %.2f\n",
//               nextCEnergyCost + cost, nextDEnergyCost + cost, probability * cProbability, probability * dProbability, exceptC, exceptD, except);
        return except;
    }
}

void getExcept(int timeSegIndex, int switchedTimes, int* classes) {
    if (timeSegIndex == timeSegSum) {
        printf("-----------------------------------\n");
        float except = calculateException(classes, -1, -1, 0, 1.0f);
        printf("classes: [");
        for(int i = 0; i < timeSegSum; i++) {
            printf("%d%s", classes[i], (i==timeSegSum-1) ? "" : " ");
        }
        printf("], switchedTimes = %d, except = %.2f\n", switchedTimes, except);
        return;
    }
    // 如果已经使用完申请
    if (switchedTimes == switchableSum) {
        classes[timeSegIndex] = classCIndeces[timeSegIndex];
        getExcept(timeSegIndex + 1, switchedTimes, classes);
    } else {
        // 想在C教室听课
        classes[timeSegIndex] = classCIndeces[timeSegIndex];
        getExcept(timeSegIndex + 1, switchedTimes, classes);
        // 在D教室听课
        classes[timeSegIndex] = classDIndeces[timeSegIndex];
        getExcept(timeSegIndex + 1, switchedTimes + 1, classes);
        
    }
}


int main() {
    timeSegSum = 3;
    switchableSum = 2;
    classroomSum = 3;
    roadSum = 3;
    // classCIndeces[i]表示时间段i上在第一节的教室编号
    int classCIndecesLocal[] = {2, 1, 2};
    classCIndeces = classCIndecesLocal;
    // classCIndeces[i]表示时间段i上在第二节的教室编号
    int classDIndecesLocal[] = {1, 2, 1};
    classDIndeces = classDIndecesLocal;
    // probabilities[i]表示时间段上从C教室换到D教室的通过概率
    float probabilitiesLocal[] = {0.8, 0.2, 0.5};
    probabilities = probabilitiesLocal;
    // roadCoast[j]表示第j条道路的信息，roadCoast[j][0]表示教室1，roadCoast[j][0]表示教室2，roadCoast[j][2]表示体力消耗
    int roadCoastLocal[3][3] = {
        {1, 2, 5},
        {1, 3, 3},
        {2, 3, 1}
    };
    roadCoast = roadCoastLocal;
    int classes[3];
    getExcept(0, 0, classes);
    return 0;
}
